from functools import cache
from typing import *
from heapq import heapify, heappop, heappush
from math import inf


class Solution:

    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:
        n = len(grid)
        s = []
        dist = [[-1] * n for _ in range(n)]
        for i in range(n):
            for j in range(n):
                if grid[i][j] == 1:
                    s.append((0, i, j))
                    dist[i][j] = 0
        while s:
            d, i, j = s.pop(0)
            for x, y in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                nx, ny = i + x, j + y
                if nx > -1 and nx < n and ny > -1 and ny < n and dist[nx][
                        ny] == -1:
                    dist[nx][ny] = d + 1
                    s.append((d + 1, nx, ny))

        s = [(-dist[0][0], 0, 0)]
        visit = [[False] * n for _ in range(n)]
        visit[0][0] = True
        while s:
            d, x, y = heappop(s)
            for i, j in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
                nx, ny = i + x, j + y
                if nx > -1 and nx < n and ny > -1 and ny < n and not visit[nx][ny]:
                    visit[nx][ny] = True
                    if nx == n - 1 and ny == n - 1:
                        return min(-d, dist[nx][ny])
                    heappush(s, (-dist[nx][ny] if -dist[nx][ny] > d else d, nx, ny))


s = Solution()
print(s.maximumSafenessFactor([[1, 0, 0], [0, 0, 0], [0, 0, 1]]))

